package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC438 {
    public static void main(String[] args) {
        System.out.println(findAnagrams2("aaaa", "bb"));
    }
    public List<Integer> findAnagrams(String s, String p) {
        int length = p.length();
        int index = 0;
        List<Integer> integers = new ArrayList<>();
        char[] chars2 = p.toCharArray();
        Arrays.sort(chars2);
        String s1 = new String(chars2);
        while (index+length<=s.length()){
            String substring = s.substring(index,index+p.length());
            char[] chars = substring.toCharArray();
            Arrays.sort(chars);
            if(new String(chars).equals(s1)){
                integers.add(index);
            }
            index++;
        }
        return integers;
    }

    public static List<Integer> findAnagrams2(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        if (p.length() > s.length()) {
            return null;
        }
        int[] ints = new int[26];
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            ints[c-'a'] ++;
        }
        int i;
        for (i = 0; i < p.length(); i++) {
            char c = s.charAt(i);
            ints[c - 'a']--;
        }
        if (check(ints)){
            list.add(i-p.length());
        }
        for(;i<s.length();i++){
            ints[s.charAt(i-p.length()+1)-'a']--;
            ints[s.charAt(i)-'a']++;
            if (check(ints)){
                list.add(i-p.length()+1);
            }
        }
        return list;
    }

    private static boolean check(int[] ints) {
        for (int anInt : ints) {
            if (anInt != 0) return false;
        }
        return true;
    }

}
